
typedef	uintptr	PageID;

typedef struct MLink MLink;
typedef struct MSpan MSpan;
typedef struct MHeap MHeap;

#define runtime_checking 1

enum {
	MaxMHeapList = (1<<20) / PAGE_SIZE,	// Maximum page length for fixed-size list in MHeap.
	HeapAllocChunk = 1<<20,		// Chunk size for heap growth
	ArenaSizeMultiple = 256<<20,

	// Number of bits in page to span calculations (4k pages).
	// On 64-bit, we limit the arena to 16G, so 22 bits suffices.
	// On 32-bit, we don't bother limiting anything: 20 bits for 4G.
#if __SIZEOF_POINTER__ == 8
	MHeapMap_Bits = (34 - PAGE_WIDTH),
#else
	MHeapMap_Bits = (32 - PAGE_WIDTH),
#endif

	// Four bits per word.
	WordsPerBitmapWord = sizeof(void*)*8/4,
	bitShift = sizeof(void*)*8/4,
};

#define MaxArena32 ((uintptr)(1<<31))

// An MSpan is a run of pages.
enum
{
	MSpanInUse = 0,
	MSpanFree,
	MSpanListHead,
	MSpanDead,
};

// A generic linked list of blocks.  (Typically the block is bigger than sizeof(MLink).)
struct MLink
{
	MLink *next;
};

struct MSpan
{
	MSpan	*next;		// in a span linked list
	MSpan	*prev;		// in a span linked list
	MSpan	*allnext;	// in the list of all spans
	PageID	start;		// starting page number
	uintptr	npages;		// number of pages in span
	MLink	*freelist;	// list of free objects
	uint32	ref;		// number of allocated objects in this span
	uint32	sizeclass;	// size class
	uint32	state;		// MSpanInUse etc
	int64   unusedsince;	// First time spotted by GC in MSpanFree state
	uintptr npreleased;	// number of pages released to the OS
	byte	*limit;		// end of data in span
};

// Main malloc heap.
// The heap itself is the "free[]" and "large" arrays,
// but all the other global data is here too.
struct MHeap
{
	Lock;
	MSpan free[MaxMHeapList];	// free lists of given length
	MSpan large;			// free lists length >= MaxMHeapList
	MSpan *allspans;

	// span lookup
	MSpan *map[1<<MHeapMap_Bits];

	// range of addresses we might see in the heap
	runtime_Mem_Area arena;
	byte *bitmap;
	uintptr bitmap_mapped;
	byte *arena_start;
	byte *arena_used;
	byte *arena_end;

	FixAlloc spanalloc;	// allocator for Span*
};

extern struct MHeap runtime_mheap;

void	runtime_MSpan_Init(MSpan *span, PageID start, uintptr npages);

// Every MSpan is in one doubly-linked list,
// either one of the MHeap's free lists or one of the
// MCentral's span lists.  We use empty MSpan structures as list heads.
void	runtime_MSpanList_Init(MSpan *list);
bool	runtime_MSpanList_IsEmpty(MSpan *list);
void	runtime_MSpanList_Insert(MSpan *list, MSpan *span);
void	runtime_MSpanList_Remove(MSpan *span);	// from whatever list it is in

void	runtime_MHeap_Init(MHeap *h);
MSpan*	runtime_MHeap_Alloc(MHeap *h, uintptr npage, int32 sizeclass, int32 acct);
void	runtime_MHeap_Free(MHeap *h, MSpan *s, int32 acct);
void*	runtime_MHeap_SysAlloc(MHeap *h, uintptr n);

MSpan*	runtime_MHeap_Lookup(MHeap *h, void *v);
MSpan*	runtime_MHeap_LookupMaybe(MHeap *h, void *v);

// Helper functions for bitmap manipulation.
void runtime_markspan(MHeap *h, void *v, uintptr size, uintptr n, bool leftover);
void runtime_unmarkspan(MHeap *h, void *v, uintptr n);
void runtime_markallocated(MHeap *h, void *v, uintptr n, bool noptr, bool atomic);
void runtime_markfreed(MHeap *h, void *v, uintptr n, bool atomic);
void runtime_checkfreed(MHeap *h, void *v, uintptr n);

// Span lookup.
int32 runtime_mlookup(MHeap *h, void *v, byte **base, uintptr *size, MSpan **sp);

// Bits in per-word bitmap.
// #defines because enum might not be able to hold the values.
//
// Each word in the bitmap describes WordsPerBitmapWord words
// of heap memory.  There are 4 bitmap bits dedicated to each heap word,
// so on a 64-bit system there is one bitmap word per 16 heap words.
// The bits in the word are packed together by type first, then by
// heap location, so each 64-bit bitmap word consists of, from top to bottom,
// the 16 bitSpecial bits for the corresponding heap words, then the 16 bitMarked bits,
// then the 16 bitNoPointers/bitBlockBoundary bits, then the 16 bitAllocated bits.
// This layout makes it easier to iterate over the bits of a given type.
//
// The bitmap starts at mheap.arena_start and extends *backward* from
// there.  On a 64-bit system the off'th word in the arena is tracked by
// the off/16+1'th word before mheap.arena_start.  (On a 32-bit system,
// the only difference is that the divisor is 8.)
//
// To pull out the bits corresponding to a given pointer p, we use:
//
//	off = p - (uintptr*)mheap.arena_start;  // word offset
//	b = (uintptr*)mheap.arena_start - off/wordsPerBitmapWord - 1;
//	shift = off % wordsPerBitmapWord
//	bits = *b >> shift;
//	/* then test bits & bitAllocated, bits & bitMarked, etc. */
//
#define bitAllocated		((uintptr)1<<(bitShift*0))
#define bitNoPointers		((uintptr)1<<(bitShift*1))	/* when bitAllocated is set */
#define bitMarked		((uintptr)1<<(bitShift*2))	/* when bitAllocated is set */
#define bitSpecial		((uintptr)1<<(bitShift*3))	/* when bitAllocated is set - has finalizer or being profiled */
#define bitBlockBoundary	((uintptr)1<<(bitShift*1))	/* when bitAllocated is NOT set */

#define bitMask (bitBlockBoundary | bitAllocated | bitMarked | bitSpecial)

typedef struct MBits
{
	uintptr offset;
	uintptr *bitmap_ptr;
	uintptr shift;
} MBits;

static inline void runtime_bits_init(MBits *b, MHeap *h, void *p) {
	byte *start = h->arena_start;

	b->offset = (uintptr*)p - (uintptr*)start;  // word offset
	b->bitmap_ptr = (uintptr*)start - b->offset/WordsPerBitmapWord - 1;
	b->shift = b->offset % WordsPerBitmapWord;
}

static inline bool runtime_bits_read(MBits *b, uintptr bit) {
	return ((*(b->bitmap_ptr) >> b->shift) & bit) != 0;
}

static inline void runtime_bits_set(MBits *b, uintptr bits, bool atomic) {
	if (!atomic) {
		*(b->bitmap_ptr) |= (bits << b->shift);
	} else {
		uintptr old_bits, new_bits;
		for (;;) {
			old_bits = *(b->bitmap_ptr);
			new_bits = old_bits | (bits << b->shift);

			if (__atomic_compare_exchange_n(b->bitmap_ptr, &old_bits, new_bits, false, __ATOMIC_SEQ_CST, __ATOMIC_ACQUIRE))
				break;
		}
	} 
}

static inline void runtime_bits_clear(MBits *b, uintptr bits, bool atomic) {
	if (!atomic) {
		*(b->bitmap_ptr) &= ~(bits << b->shift);
	} else {
		uintptr old_bits, new_bits;
		for (;;) {
			old_bits = *(b->bitmap_ptr);
			new_bits = old_bits &~ (bits << b->shift);

			if (__atomic_compare_exchange_n(b->bitmap_ptr, &old_bits, new_bits, false, __ATOMIC_SEQ_CST, __ATOMIC_ACQUIRE))
				break;
		}
	}
}

static inline void runtime_bits_assign(MBits *b, uintptr bits, bool atomic) {
	if (!atomic) {
		runtime_bits_clear(b, bitMask, false);
		runtime_bits_set(b, bits, false);
	} else {
		uintptr old_bits, new_bits;

		for (;;) {
			old_bits = *(b->bitmap_ptr);
			new_bits = (old_bits &~ (bitMask << b->shift)) | (bits << b->shift);

			if (__atomic_compare_exchange_n(b->bitmap_ptr, &old_bits, new_bits, false, __ATOMIC_SEQ_CST, __ATOMIC_ACQUIRE))
				break;
		}
	}
}

static inline void runtime_bits_next(MBits *b, uintptr size) {
	size /= sizeof(void *);

	b->bitmap_ptr -= (size / WordsPerBitmapWord);
	size %= WordsPerBitmapWord;

	uintptr s = (b->shift + size) % WordsPerBitmapWord;
	if (s < b->shift) {
		b->bitmap_ptr--;
	}
	b->shift = s;
}
